package main

/*
startIdx 需要从当前遍历的继续开始，
什么意思呢，就是因为所有值可以重复选，
但又是组合问题，所以是从当前开始可以重选，
从头开始的话就变成组合了
*/
var (
	ans39  [][]int
	path39 []int
	c39    []int
)

func combinationSum(candidates []int, target int) [][]int {
	c39 = candidates
	ans39 = make([][]int, 0)
	bt39(0, target, 0)
	return ans39
}

func bt39(sum, target, startIdx int) {
	if sum == target {
		tmp := make([]int, len(path39))
		copy(tmp, path39)
		ans39 = append(ans39, tmp)
	} else if sum > target {
		return
	}

	for i := startIdx; i < len(c39); i++ {
		path39 = append(path39, c39[i])
		sum += c39[i]
		bt39(sum, target, i)
		sum -= c39[i]
		path39 = path39[:len(path39)-1]
	}
}
